import java.util.Arrays;
import java.util.Comparator;


// 分数背包问题
public class FractionalKnapsackProblem {
    static class Item{
        int value;
        int index;
        int weight;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitPrice(){
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "value=" + value +
                    ", index=" + index +
                    ", weight=" + weight +
                    '}';
        }
    }

    public static void select(Item[] items, int total){
        Arrays.sort(items, Comparator.comparingInt(Item::unitPrice).reversed());
        int max = 0;
        for (Item item : items){
            if (total - item.weight > 0){ // 拿的完
                max += item.value;
                total -= item.weight;
            }else {  // 拿不完
                max += total * item.unitPrice();
                break;
            }
        }
        System.out.println("最高价值为：" + max);
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 4, 24),
                new Item(1, 8, 160),
                new Item(2, 2, 4000),
                new Item(3, 6, 108),
                new Item(4, 1, 4000),
        };
        select(items, 10);
    }
}
